\documentclass[]{article}
\usepackage{fullpage}
\usepackage{color}
\newcommand{\structure}[1] {\paragraph{\textcolor{red}{#1}}}
%opening
\title{Mixed Integer Programming Accelerator}
\author{Igor Zarivach \and Shlomo Moran \and Yossi Shiloach}
\date {\today}
\begin{document}
%\tableofcontents
\maketitle

\begin{abstract}

\end{abstract}


\section{Introduction}
\structure{Move 1: Establishing a territory \\
Step 1  Claiming importance and/or}
Optimization is the task of finding an optimal solution to a problem that has many alternative solutions. Mixed Integer Programming is an important tool for modeling and solving combinatorial optimization problems in various fields, such as transportation, production, scheduling, network layout and many others. ~\cite{RefWorks:31}
\structure{
Step 2  Making topic generalizations and/or \\
}
Solving MIP for optimality is NP-hard ~\cite{garey2002computers}.  Recent advances in the implementation of algorithms and hardware improvements have extended the size of MIP programs that can be solved efficiently using today's computers.

However, there are still hard problems that can't be solved efficiently. MipLib, an open library of MIP problems, contains a standard test set used to compare the performance of MIP optimizers.
MIPLib classifies instances into three categories: easy for those that can be solved
within an hour on a contemporary PC with a state of the art solver, hard for those
that are solvable but take a longer time, and finally open instances for which the optimal solution is not known. As for 2010, there were still 42 hard, and 134 open problems. \cite{MipLib}

When the problem is computationally hard, a heuristic is used. Modern MIP solvers implement several heuristics in order to find a feasible solution. Heuristics are categorized by their functionality, for instance, a \emph{start} heuristic finds an initial solution, while an \emph{improvement} heuristic finds a better solution, given some feasible solution. Moreover, there are specific and general purpose heuristics: a specific heuristic uses the problem knowledge, whereas a general purpose heuristic has no information about the problem itself, and uses only the mathematical model.\\
It is generally accepted that specific heuristic is faster, on the other hand, a general purpose heuristic is more versatile, since it doesn't require the deep problem understanding and can solve any optimization problem.\\
Additional attribute of a heuristic is the speed. The faster it finds a feasible solution, the better. Finally, the quality of the solution is important: possessing a good solution early in the solving process increases the efficiency of a MIP solver.  

\structure{
Step 3  Reviewing items of previous research\\ 
}
Several general purpose heuristics were published recently. Local branching (Fishetti and Lodi 2002) ~\cite{RefWorks:30}, relaxation induced neighborhood search (RINS) ~\cite{RefWorks:29} (Danna et al. 2005) and the evolutionary algorithm for polishing MIP solutions (Rothberg 2007) ~\cite{rothberg2007evolutionary} are general purpose improvement heuristics. Local branching and RINS explore the local neighborhood of the given solution to find better solutions. Polishing algorithm generates a new population of feasible solutions by selecting, combining and mutating a previous generations of solutions.\\
Comparison of general purpose vs problem specific heuristics ???
\structure{
Move 2: Establishing a niche\\
Step 1a  Counter-claiming or \\
Step 1b  Indicating a gap or \\
Step 1c  Question-raising or \\
Step 1d  Continuing a tradition\\ 
}
Heuristics should find good solutions fast. It is not unusual to have a time limit of less than a hour per instance for hard problems with hundreds of instances. The solution quality will probably be far from the optimal. Having the tight time constraint and a given general purpose heuristics, can we improve the solution quality by providing the knowledge about the problem itself?
    
In this research we propose a simple general purpose fixing heuristic for finding "good" feasible solutions for MIP models. We implement several improvements to tune the heuristics for the best performance. Then, we supply some problem knowledge by assigning attributes to MIP variables. We compare the heuristics to other improvement heuristics and analyze the results.\\
\structure{
Move 3: Occupying the niche\\
Step 1a  Outlining purposes or \\
Step 1b  Announcing present research \\
Step 2  Announcing principle findings \\
Step 3  Indicating article structure\\
}

\section{Prewriting}
\subsection{Purpose}
\subsubsection{What is the topic?}
The topic is: solving hard MIP problems fast by using simple heuristics. 
\subsubsection{What is the problem?}
Real MIP problems are hard and solving them with state of the art solvers on expensive hardware takes too much time. 
\subsubsection{Why am I writing about it?}
Because it is beneficial to find solutions to hard problems in limited time. The factory needs to produce goods and it must to decide about the allocation of its resources to achieve objectives.
If the model is hard, the heuristic is necessary. Existing heuristics do a good job, but can we do better? Will simple generic heuristic be as effective as domain aware heuristic? 
\subsubsection{Why is this important?}
There are many real world problems that are modeled by MIP and solved. 
\subsection{Audience}
\subsubsection{Who is my audience?}
My audience is researchers, students and general public interested in the optimization area. 
\subsubsection{What do they know about the topic?}
They know about the modeling in optimization, solving MIP theory, branch and bound variations,  solvers architecture, different heuristics. 
\subsubsection{What should they know about the topic? Prerequisites? Or our contribution?}
They should know how our heuristic works, why is it simple, how do we measure its performance,its advantages and disadvantages and in which cases it is better than other methods. 
\subsection{Planning and Ideas}
\begin{itemize}
\item Operational research, what problems does it solve in what areas http://www.crcnetbase.com/isbn/9781420091878
\item Mathematical modeling, Constraint satisfaction and SAT
\item Linear programming, Integer programming, Mixed integer programming
\item Student assignment problem, how many variables, is it hard? MipLib categorization of hard MIP
\item Heuristics definition, heuristics in MIP, heuristics using sub MIP, fixing
\item Experimental analysis of heuristic methods, what statistics are collected, how information is analyzed and presented
\item Random heuristics, statistical methods for analysis
\item Branch \& bound \& cut,  Polish genetic algorithm, state of the art, who uses it
\item Generic vs problem aware heuristics, advantages
\item Naive fixing description, CPLEX as a black box, fixing fraction, iteration time, changing parameters (simulated annealing temperature)
\item Software architecture, Java CPEX interfaces 
\item Domain based fixing, modeling of fixing constraint, choosing the fixed variable set
\item Comparison of naive vs domain aware fixing, naive vs polish, domain vs polish
\item Comparison of fixing vs local branching? Need local branching implementation 
\item Benchmarking, what is it, which MIP problems, platform, results presentation
\end{itemize} 

\section{Operational Research}
"Operations research is concerned with scientifically deciding how to best design
and operate man machine systems, usually under conditions requiring the allocation
of scarce resources." Definition by Operations Research Society of America.\\
The Operational Research Society of Great
Britain has adopted the following definition:
"Operational research is the application of the methods of science to complex
problems arising in the direction and management of large systems of men,
machines, materials and money in industry, business, government, and defense."
Operations or Operational Research starts from World War II planning of army operations such as deployment of ships against enemy submarines, deployment of radars and air defense bases. ~\cite{RefWorks:31} 
\paragraph*{} Due to their success in military planning, industry, business and academy adopted these scientific methods. For instance, scientists used OR methods to plan petroleum production and transportation.\\
Operations research had a major breakthrough with appearance of electronic computers, that made it possible to solve more complex problems. Additional success factor was the academic research and development of theories and algorithms, such as linear programming, netwrok flows, dynamic and integer programming. These theories assist to create mathematical models for complex business and industry problems. Mathematical models are easier to analyze and simulate with different parameters.
Scientists analyze and solve mathematical models, classify them by their complexity and find suitable models for real world, large scale systems.

\paragraph{Airline Optimization} 
Airlines use optimization tools (OR) to plan and schedule business processes for better profitability. Some applications are the management of cargo, crew scheduling, strategic planning, revenue forecasting and tickets reservations. Optimization has major financial benefits for airline companies, in light of growing air traffic and increasing competition, saving millions of dollars.\\
Typical airline planning process consists of four sub processes, with different time horizons ~\cite{RefWorks:32}:
\begin{description}
\item[Resource planning] is concerned with strategic planning of flying locations, aircraft aquisition, manpower training. Time horizon is one to two years.
\item[Market planning] is concerned with aircraft assignment, schedule and revenue decisions. Time horizon is six months.
\item[Operations planning] is concerned with aircraft routing and airport operations. Time horizon is a month.
\item[Operations control] is concerned with airport operations, aircraft rerouting and customer service. Time horizon is two weeks.
\end{description}
Each of these complex problems is modeled and solved independently, due to the computational complexity of the whole problem. However, the integrated solution might be suboptimal. \\
OR tools are not used for strategic planning due to lack of accurate traffic forecast, market profitability and competitive information. Airlines deploy optimization methods in fleet assignment and crew scheduling problems.
\paragraph{Fleet assignment}
Once airline decides on the origin, destination and timetable of flights, it needs to allocate aircraft from its fleet for each flight. The objective is to maximize profitability, complying with operational constraints. OR tools model the problem with mixed integer program and solve with MIP exact or heuristic methods.   
\paragraph{Aircraft routing}
To minimize operation costs, airlines schedule the same aircraft for several flights daily. Routing problem is to allocate specific vehicle to sequencial flights, complying with operational and maintenance requirements. There are several types of required safety maintenance inspections for every aircraft, performed periodically, with checks duration from few hours to several days.
The problem is modeled by multicommodity flow problem or as a set partitioning problem. 
\paragraph{Crew scheduling}
The objective of the crew scheduling problem is to minimize the cost of crew assignment to flights. The requirements are the necessary roles(pilots) and union regulations, such as a limit of shift working hours. Personal preferences are also included. The cost of assignment is based on several factors, such as salary and hotel expenses. This problem is modeled and solved as a set partitioning problem.

\paragraph{Recovery from irregular operations}
When unexpected events happen and affect the flight timetable by cancelling or delaying flights, airlines must react to minimize expenses. The time is a crucial factor to produce a fast recovery plan and resume scheduled flights. Usually, companies must implement the first found solution due to time pressures.      
  
\paragraph{Aircraft load planning}
Aircraft load planning problem requires to transport equipment and people from a set of locations to a set of destinations with minimal number of aircraft loads. Additional requirements are safe combinations of materials, available floor space for loading the cargo, speed and ease of loads. 
It is important to arrange the containers such that the loaded aircraft will have efficient fuel consumption. The loading problem is modeled by packing problems, which are usually hard, even in one dimension (knapsack and bin packing). 

\section{Introduction}
\paragraph{Move 1: Establishing a territory} 
\textrm{} \\ 
Step 1  Claiming importance and/or \\
Step 2  Making topic generalizations and/or \\
Step 3  Reviewing items of previous research 

\paragraph{Move 2: Establishing a niche}
\textrm{} \\ 
Step 1a  Counter-claiming or \\
Step 1b  Indicating a gap or \\
Step 1c  Question-raising or \\
Step 1d  Continuing a tradition 

\paragraph{Move 3: Occupying the niche}
\textrm{} \\ 
Step 1a  Outlining purposes or \\
Step 1b  Announcing present research \\
Step 2  Announcing principle findings \\
Step 3  Indicating article structure

Solving MIP for optimality is hard \cite{garey2002computers}. Therefore heuristics are used to:
\begin{enumerate}
\item Improve feasible solution
\end{enumerate}

\section{MIP - Mixed Integer Programming}
TBD

\section{MIP Solving Methods}
 The MIP optimization problem is NP-hard ~\cite{garey2002computers}, so there is no known polynomial algorithm that finds the optimal integer solution. However, there are methods that can find near optimal integer solution effectively in practice.


\subsection{Branch and bound}
Branch and bound (B\&B) is a divide and conquer technique for finding the optimal solution on a general MIP problem ~\cite{Wolsey}. B\&B efficiently enumerates the solution space, pruning unpromising solution sets.

We consider a minimization MIP problem. B\&B explores a solution set defined by the relaxed MIP using the Simplex method. B\&B solves the relaxed MIP problem to find the lower bound of objective function. 
If a feasible solution exists with objective value better then the lower bound,  If the solution is integral and feasible for the MIP problem, the solution is optimal. Otherwise, the idea is to divide the problem to smaller MIP problems (branching) and optimize them recursively.\\
The recursion stops on sub-MIP problems that should not be divided further. Main ideas of the branch and bound are summarized below.

\paragraph{The tree}
The solver enumerates solutions using the enumeration tree. Nodes of the tree represent MIP problems. The tree grows from the root, the original problem with all feasible solutions set. Every time a problem is divided to new MIP subproblems, new child nodes are added to the tree. Child nodes represent the MIP problem of the parent node with an additional constraint.

\paragraph{The incumbent solution and pruning}
The incumbent solution is the best feasible solution found so far in the process of branch and bound. Branch and bound finds feasible solutions either from solving LP relaxation or by heuristics.
Having the incumbent solution with good objective value will improve the search performance significantly by discarding subproblems which have inferior solutions to the incumbent. Pruning is one of the most important aspects of branch and bound since it is precisely what prevents the search tree from growing exponentially.

\paragraph{The search algorithm}
The solver traverses the tree starting from the root. The traversal decides whether the node should be branched or pruned. While at some tree node, the solver uses LP relaxation to find a lower bound on the optimal solution in the current sub MIP problem. There are several cases to consider:
\begin{itemize}
\item The problem is unbounded. Then the original problem is unbounded and the solver stops the traversal.
\item The problem's optimal solution is not better than the best solution found so far, the incumbent.
Then there is no need to continue the tree traversal from the current node. The current node is pruned.
\item The problem's lower bound improve the best solution found so far. Then the traversal continues from the current node and branching will be later performed.
\item The problem is infeasible. The node is pruned.
\end{itemize}

\paragraph{Branching}
Given a fractional solution to LP relaxation, the algorithm chooses some variable $x_i$ that is restricted to be integer, but whose value in the LP relaxation is fractional $f$. Then the problem is divided to two different subproblems:
\begin{enumerate}
\item By adding a constraint $x_i\le \lfloor{f}\rfloor$
\item By adding a constraint $x_i\ge \lceil{f}\rceil$
\end{enumerate}

\paragraph{Lower and upper bounds gap}
During the search, the solver maintains both lower and upper bounds on the optimal solution.  The lower bound is obtained by taking the minimum of the lower bounds of the current leaf nodes. The upper bound is the lowest objective value solution found so far, the value of the incumbent.
The difference between the current upper and lower bounds is known as the gap. When the gap is zero, the solver has found the optimal solution.


\subsection{Cutting planes}
This method works by adding additional constraints to the model. The MIP problem is relaxed and the relaxed LP problem is solved. If the solution is fractional, we add a new constraint which removes the fractional optimal solution, but doesn't change the feasible set of integral solutions.
Then, the process is continued until an integer solution is finally found.
Cutting plane methods have proved not very successfull on large problems.

\section{MIP heuristics}
There are several types of MIP solving heuristics.\\
We are interested in the \emph{improvement heuristics}, which guide the search algorithm to better solution, given some incumbent.\\
Relaxation induced neighbourd search (RINS) \cite{RefWorks:29} uses the fixing technique to solve a smaller MIP. The heuristic is integrated into the branch and cut search algorithm.
It uses an incumbent and relaxed LP solution to fix the value of variables with the same values in both solutions. RINS solves the smaller sub MIP with MIP solver to get a better incumbent. The advantage of this technique over the random choice of variables is due to the choice of the neighborhood around both the incumbent and the continuous relaxation solution.\\
Another difference is the truncation of the sub MIP solving. RINS limits the number of branch and cound tree nodes processed in every iteration, not the processor or clock time.\\\\
Local branching \cite{RefWorks:30} heuristics searches the incumbent's neighbourhood for better solutions. This heuristic is integrated into the branch and cut tree search and starts in a tree node when the incumbent is found. 
Having an incumbent, the algorithm creates a new sub MIP with additional linearized constraint:
$$\sum_{i\in B}|x_i-x^*_i| \le r$$
where $x^*$ is the incumbent, $r$ is the radius of the neighbourhood and $B$ is a set of binary variables indices. The search process is truncated by the number of tree nodes. When sub MIP is not solved to optimality due to the node limit, the search radius is halved. The process stops when the radius equals 5.

\section{Local branching}
Local branching \cite {RefWorks:30} is the MIP enumeration technique focusing on finding reasonable feasible solutions as early as possible. It is a two level branching method, on a higher level it partitions the solution space using the local neighborhood of a  feasible solution. The lower level enumeration is left for a black box MIP solver, such as IBM CPLEX, which performs B\&B exact enumeration. 
Local branching technique was effective on several hard MIP instances and found better solutions than CPLEX solver. The technique is exact, and performs a systematic search of the solution space, therefore proving the solution optimality. Local branching requires an initial feasible solution for starting the enumeration.
 
Regular B\&B divides the solution space (branches) according to a chosen fractional variable in the relaxed problem solution. For a fractional $x_i=f$, the B\&B divides the original solution set to two subsets:
$x_i \ge \lceil f \rceil$ 
and 
$x_i \le \lfloor f \rfloor$. Each subset is explored recursively. 
Local branching divides the set of solutions by defining a local $k$-$OPT$ neighborhood $N(s_0,k)$ of the given feasible solution $s_0$. The neighborhood is a set of feasible solutions of the MIP with an additional constraint:
$$\Delta(x,s_0) := |S|{} \le k$$
$$S := \{i \textrm { $|$  $x_i$ is binary, } x_i \ne s_i , 1 \le i \le n\}$$

\paragraph{Soft fixing vs Hard fixing}
Given a feasible solution to a MIP problem, the problem can be reduced to smaller size by fixing a subset of integral variables to their values in initial solution. Optimal solution for reduced MIP problem (sub-MIP) is feasible for original MIP. Clever choice of fixed variables leads to better feasible solutions.

Hard fixing is a method of choosing which variables to fix based on heuristics method. On the contrary, soft fixing method models this decision by linear equation and uses a black box MIP solver to determine the fixing by solving a new MIP problem. For example, given a solution $x^0$ for 0-1 MIP model and fixing fraction of $0.8$, soft fixing will add the constraint
$$\displaystyle \sum_{j=1}^n x^0_j\cdot x_j \le \lceil 0.8\sum_{j=1}^n x^0_j \rceil$$ 
to original MIP problem.
Local branching uses the soft fixing technique to improve a given feasible solution. 
%\begin{table}
%\begin{tabular}{|c|c| c|}
%\hline
%Type & Name & Description \\
%\hline
%Bottom && \\
%\hline

%\end{tabular}
%\end{table}

\section{Our heuristics}
\paragraph{}

\section{Designing the benchmarking}
\paragraph{Goals}
\begin{enumerate}
\item Is the cruncher fast? Does it produce solutions fast?
\item Is the quality of the best solution good (accuracy)? 
\item Is it robust? Does the performance change on different problems? 
\item Is it innovative? 
\item Is it simple?
\end{enumerate}

\paragraph{Comparing algorithms}
The cruncher is an improvement heuristics, so we compare it with other improvement heuristics, the Local Branching \cite{RefWorks:30}.
We also compare it with the genetic heuristics, the polish \cite{rothberg2007evolutionary}, implemented in the CPLEX solver.
 
\paragraph{Measuring performance}
We collect performance measurements from three categories, based on \cite{RefWorks:36}.
\subparagraph{Quality of solutions}
\begin{enumerate}
\item The objective value of the best solution

\item The best solution gap from either optimal (if known) or lower bound.
\end{enumerate}
\subparagraph{Computational effort}
\begin{enumerate}
\item Quality versus time plot, the change of the objective value in time (user time)
\item Time to the best found solution (user time)
\item The ratio of time to produce a solution within 5\% of the best \\ $r_{0.05}=\frac{\textrm{time to within 5\% best}}{\textrm{time to best found}}$
\item Total number of B\&C tree nodes processed

\end{enumerate}

\subparagraph{Robustness}
We benchmark the following test problems
\begin{enumerate}
\item MIPLib ~\cite{MipLib} (hard problems)
\item Student assignment
\item Convex coloring
\end{enumerate}

\paragraph{Factors to test}
Cruncher uses few parameters (factors) influencing the performance. We test the impact of the following:
\begin{enumerate}
\item Initial fixing fraction
\item Iteration time
\item Solution pool size
\item Fix to one vs Fix to any
\item Domain based vs random fixing
\end{enumerate}

\subparagraph{Environment factors}
All benchmarking experiments are done on HP Pavilion 15 Notebook PC with 8.00 GB RAM, 64 bit, Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz and
IBM CPLEX 12.5.0.0.  

\paragraph{Choosing the experimental design}
 
\pagebreak

\nocite{*}
\bibliographystyle{alpha}
\bibliography{Thesis}

\end{document}
